package com.leetcode.algorithm.y22.m06;

/**
 * 1014. 最佳观光组合
 * 
 * https://leetcode.cn/problems/best-sightseeing-pair/
 * 
 * @author jie.deng
 *
 */
class Question1014Solution01 {

	// 2 <= values.length <= 50000
	public int maxScoreSightseeingPair(int[] values) {
		int len = values.length;
		int[] dp = new int[len];
		dp[1] = values[1] + (values[0] - 1);
		for (int i = 2; i < len; i++) {
			// 从j到i：f(j,i-1) >= max(f(0...i-2,i-1)) 则 f(j,i) >= max(f(0...i-2,i))
			// 从i-1到i
			dp[i] = values[i] + Math.max(dp[i - 1] - values[i - 1] - 1, values[i - 1] - 1);
		}

		int maxScore = dp[1];
		for (int i = 2; i < len; i++) {
			if (dp[i] > maxScore) {
				maxScore = dp[i];
			}
		}
		return maxScore;
	}

}